package com.beney.al;

public class DivChessConquer {
  public static void main(String[] args) {
    int size = 4;
    int[][] board = new int[size][size];
    chessBoard(board, size, 0, 0, 0, 0);
    display(board, size);
  }

  private static int tile;

  private static void display(int[][] board, int size) {
    for (int i = 0; i < size; ++i) {
      for (int j = 0; j < size; ++j) {
        System.out.print(board[i][j] + "\t");
      }
      System.out.println("");
    }
    System.out.println("");
  }

  /**
   * 分治法，每一次将棋盘一分为四
   *
   * @param board 棋盘
   * @param size  当前棋盘大小
   * @param tr    棋盘左上角的row
   * @param tc    棋盘左上角的column
   * @param dr    特殊方格的row
   * @param dc    特殊方格的column
   */
  private static void chessBoard(int[][] board, int size, int tr, int tc, int dr, int dc) {
    if (size <= 1) return;
    tile += 1;

    // 这一步非常细节，非常坑！不能直接使用全局变量tile来作为赋值
    // 因为之后的操作涉及到递归而且没有回溯tile的值！！
    // 所以全局变量tile会在我们预期之外增加
    int curTile = tile;
    size /= 2;  // 每一将棋盘一分为4，故size为原本的1/2

    // 棋盘划分为了4大部分
    if (dr < tr + size && dc < tc + size) { // 特殊方格在划分后棋盘的左上角
      chessBoard(board, size, tr, tc, dr, dc);
    } else {
      int conquerR = tr + size - 1, conquerC = tc + size - 1;
      board[conquerR][conquerC] = curTile;
      chessBoard(board, size, tr, tc, conquerR, conquerC);
    }
    if (dr < tr + size && dc >= tc + size) { // 特殊方格在划分后的右上角
      chessBoard(board, size, tr, tc + size, dr, dc);
    } else {
      int conquerR = tr + size - 1, conquerC = tc + size;
      board[conquerR][conquerC] = curTile;
      chessBoard(board, size, tr, tc + size, conquerR, conquerC);
    }
    if (dr >= tr + size && dc < tc + size) {    // 特殊方格在划分后的左下角
      chessBoard(board, size, tr + size, tc, dr, dc);
    } else {
      int conquerR = tr + size, conquerC = tc + size - 1;
      board[conquerR][conquerC] = curTile;
      chessBoard(board, size, tr + size, tc, conquerR, conquerC);
    }
    if (dr >= tr + size && dc >= tc + size) {   // 特殊方格在划分后的右下角
      chessBoard(board, size, tr + size, tc + size, dr, dc);
    } else {
      int conqerR = tr + size, conquerC = tc + size;
      board[conqerR][conquerC] = curTile;
      chessBoard(board, size, tr + size, tc + size, conqerR, conquerC);
    }
  }
}
